package interview.tree;

//遍历
public class TreeTraversal
{
	// 前序遍历
	public void preOrder(TreeNode root)
	{
		// 处理特殊值
		if (root == null)// 空树
		{
			return;// 什么都不能输出
		}

		// 先遍历根:输出
		System.out.print(root.getValue());
		// 前序遍历左子树
		preOrder(root.getLeft());
		// 前序遍历右子树
		preOrder(root.getRight());
	}

	// 中序遍历
	public void inOrder(TreeNode root)
	{
		// 处理特殊值
		if (root == null)// 空树
		{
			return;// 什么都不能输出
		}

		// 先中序遍历左子树
		inOrder(root.getLeft());
		// 遍历根:输出
		System.out.print(root.getValue());
		// 中序遍历右子树
		inOrder(root.getRight());
	}

	// 后序遍历
	public void postOrder(TreeNode root)
	{
		// 处理特殊值
		if (root == null)// 空树
		{
			return;// 什么都不能输出
		}

		// 先后序遍历左子树
		postOrder(root.getLeft());
		// 后序遍历右子树
		postOrder(root.getRight());
		// 遍历根:输出
		System.out.print(root.getValue());
	}

	public String postOrder(String preOrder, String inOrder)// 不建树
	{
		// 处理特殊情况
		if (preOrder.isEmpty())// 空传——>空树:没有结点
		{
			return "";
		}

		// 前序遍历的第一个点：根(A)
		char rootValue = preOrder.charAt(0);// 拿出第一个字符:根的value
		// 从中序遍历中寻找根(A)；找到后，切分左右
		int rootIndex = inOrder.indexOf(rootValue);
		// 知道左子树的长度(从中序那里看)
		// int leftSize = rootIndex;

		return
		// 先后序遍历左子树，返回左子树后序遍历的序列
		postOrder(preOrder.substring(1, 1 + rootIndex), inOrder.substring(0, rootIndex)) +
		// + 右子树后序遍历的序列
				postOrder(preOrder.substring(1 + rootIndex), inOrder.substring(1 + rootIndex)) + rootValue;

	}

	public static void main(String[] args)
	{
		TreeCreator creator = new TreeCreator();
		TreeTraversal traversal = new TreeTraversal();

		System.out.println("Sample tree traversal");
		TreeNode sampleTree = creator.createSampleTree();
		// 先序遍历
		traversal.preOrder(sampleTree);
		System.out.println();

		// 中序遍历
		traversal.inOrder(sampleTree);
		System.out.println();

		// 后序遍历
		traversal.postOrder(sampleTree);
		System.out.println();

		System.out.println("====================================");
		System.out.println("Creating tree from preOrder and inOrder");
		TreeNode tree = creator.createTree("ABDEGCF", "DBGEACF");
		traversal.postOrder(tree);// 后序遍历
		System.out.println();
		// 边界值测试
		traversal.postOrder(creator.createTree("", ""));// 空树
		System.out.println();
		traversal.postOrder(creator.createTree("A", "A"));// 单结点
		System.out.println();
		traversal.postOrder(creator.createTree("AB", "BA"));// 把树根放到最后，看1 + rootIndex是否越界
		System.out.println();

		System.out.println("====================================");
		System.out.println("Generating postOrder directly");
		System.out.println(traversal.postOrder("ABDEGCF", "DBGEACF"));
		System.out.println(traversal.postOrder("", ""));
		System.out.println(traversal.postOrder("A", "A"));
		System.out.println(traversal.postOrder("AB", "BA"));
	}

}
